package treenode;

import msbd.ListNode;
import sun.reflect.generics.tree.Tree;

import java.util.*;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:
 * User:Mr.Du
 * Date:2021/8/20
 * Time:18:42
 */
public class CopyTreeNode {
    

    public static void main(String[] args) {
        System.out.println(Integer.MIN_VALUE);
        int input = 0;
        LinkedList<Integer> list = new LinkedList<>();
        Scanner sc = new Scanner(System.in);
        //当输入-1时，表示结束输入
        while(sc.hasNextLine()){
            if((input = sc.nextInt()) != -1){
                list.add(input);
            }else {
                break;
            }
        }

        TreeNode binaryTree = createBinaryTree(list);
        System.out.println("层序遍历输出创建的二叉树");
        List<List<Integer>> lists = levelOrder(binaryTree);
        printTreeNode(lists);
        System.out.println("========================");
        //copy
        TreeNode newTree = copyTree(binaryTree);
        System.out.println("复制后输出新的二叉树 newTree :");
        List<List<Integer>> newTreeList = levelOrder(newTree);
        printTreeNode(newTreeList);

        System.out.println("叶子结点个数: ");
        System.out.println(countLeaf(binaryTree));

        System.out.println("结点个数: ");
        System.out.println(count(binaryTree));

        System.out.println("左右子树个数: ");
        System.out.println(DsonNode(binaryTree));
    }


    /**
     * 统计叶子
     * @param root
     * @return
     */
    public static int countLeaf(TreeNode root){
        if(root == null) return 0;
        else if (root.leftChild == null && root.rightChild == null)
            return 1;
        return countLeaf(root.leftChild) + countLeaf(root.rightChild);
    }


    /**
     * 统计结点
     * @param root
     * @return
     */
    public static int count(TreeNode root){
        if(root == null) return 0;
        return 1 + count(root.leftChild) + count(root.rightChild) ;
    }

    /**
     * 统计子树个数
     * @param root
     * @return
     */
    public static int DsonNode(TreeNode root){
        if(root == null) return 0;
        else if(root.leftChild != null && root.rightChild != null)
            return DsonNode(root.leftChild) + DsonNode(root.rightChild) + 1;
        return DsonNode(root.leftChild) + DsonNode(root.rightChild) ;
    }

    /**
     * 复制二叉树
     * @param root
     * @return
     */
    public static TreeNode copyTree(TreeNode root){
        TreeNode node = null;
        if(root == null) return null;
        node = new TreeNode(root.data);
        node.leftChild = copyTree(root.leftChild);
        node.rightChild = copyTree(root.rightChild);
        return node;
    }

    /**
     * 创建二叉树
     * @param list
     * @return
     */
    public static TreeNode createBinaryTree(LinkedList<Integer> list){
        TreeNode node = null;
        if(list == null || list.isEmpty()){
            return null;
        }
        Integer data = list.removeFirst();
        //0表示当前结点为空
        if(data != 0){
            node = new TreeNode(data);
            node.leftChild = createBinaryTree(list);
            node.rightChild = createBinaryTree(list);
        }
        return node;
    }

    /**
     * 层序遍历，将每层结果放在一个集合，方便查看结果
     * @param root
     * @return
     */
    public static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> levels = new ArrayList<>();
        if (root == null) return levels;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int level = 0;
        while ( !queue.isEmpty() ) {
            levels.add(new ArrayList<>());

            int level_length = queue.size();
            for(int i = 0; i < level_length; ++i) {
                TreeNode node = queue.remove();

                levels.get(level).add(node.data);

                if (node.leftChild != null) queue.add(node.leftChild);
                if (node.rightChild != null) queue.add(node.rightChild);
            }
            level++;
        }
        return levels;
    }


    public static void printTreeNode(List<List<Integer>> list){
        for(List l : list){
            System.out.println(l);
        }
    }

    private static void qianxu(TreeNode node){
        if(node == null) return;
        System.out.println(node.data);
        qianxu(node.leftChild);
        qianxu(node.rightChild);
    }
}
